
public class LongestValidParentheses {
	public void tester() {
		String a1 = "(((((((((((((()))()(((((((((((((((((((((((((((()";
		System.out.println(longestValidParentheses(a1));
	}
	
	
	
	public int longestValidParentheses(String s) {
		int a = 0, b = s.length() - 1;
		
		int current = 0;
		int max = 0;
		
		while(a < b) {
			if(s.charAt(a) == ')') {
				a++;
				current = 0;
//				System.out.println("current = 0 [1]");
			}
			else if(s.charAt(b) == '(') {
				b--;
				current = 0;
//				System.out.println("current = 0 [2]");
			}
			else if(b-a <= 2 && s.charAt(a) == '(' && s.charAt(a+1) == ')') {
				current = current + 2;
				if(current > max) max = current;
				a = a+2;
				
//				System.out.println("current += 2 [3] "+current);
			}
			else if(s.charAt(a) == '(' && s.charAt(a+1) == ')') {
				current = current + 2;
				if(current > max) max = current;
				a = a+2;
				
//				System.out.println("current += 2 [4] "+current);
			}
			else {
				int count = 0, min = Integer.MAX_VALUE;
	            for(int i = 0 ; i + a <= b ; i++) {
	                if(s.charAt(a+i) == '(') count++;
	                else {
	                	count --;
	                	if(count < min) min = count;
	                }
	                
//	                System.out.println("c: "+count);
	                if(count == 0) {
//	                	System.out.println("3: "+(i+1));
	                	current = current + (i+1);
	                	if(current > max) max = current;
	                	a = a + i + 1;
	                	break;
//	                	System.out.println("current += i [5] "+current);
	                }
	            }
	            
//	            System.out.println("a++");
	            
	            if(count != 0) {
	            	a = a+min;
	            	System.out.println("min: "+min);
		            // a++;
	            	current = 0;
	            }
	            
//	            System.out.println("current = 0 [6]");
			}
		}
		
		return max;
	}
	
	public int longestValidParentheses2(String s) {
        int a = 0, b = s.length()-1;
        while(a < b && s.charAt(a) == ')') {
            a++;
        }
        while(b > a && s.charAt(b) == '(') {
            b--;
        }
        
        if(a >= b) {
            return 0;
        }
        else if(s.charAt(a) == '(' && s.charAt(a+1) == ')' && b-a > 2) {
        	System.out.println("1: "+2);
            return 2+longestValidParentheses2(s.substring(a+2, b+1));
        }
        else if(s.charAt(a) == '(' && s.charAt(a+1) == ')') {
        	System.out.println("2: "+2);
            return 2;
        }
        else {
            int count = 0;
            for(int i = 0 ; i <= b - a ; i++) {
                if(s.charAt(a+i) == '(') count++;
                else count --;
                if(count == 0) {
                	System.out.println("3: "+(i+1));
                	return i+1+longestValidParentheses2(s.substring(a+i));
                }
            }
            return longestValidParentheses2(s.substring(a+1));
        }
    }
	
	public int longestValidParentheses3(String s) {
        int a = 0, b = s.length()-1;
        while(a < b && s.charAt(a) == ')') {
            a++;
        }
        while(b > a && s.charAt(b) == '(') {
            b--;
        }
        
        if(a >= b) {
            return 0;
        }
        else if(s.charAt(a) == '(' && s.charAt(a+1) == ')' && b-a > 2) {
        	System.out.println("1: "+2);
            return 2+longestValidParentheses3(s.substring(a+2, b+1));
        }
        else if(s.charAt(a) == '(' && s.charAt(a+1) == ')') {
        	System.out.println("2: "+2);
            return 2;
        }
        else {
            int count = 0;
            for(int i = 0 ; i <= b - a ; i++) {
                if(s.charAt(a+i) == '(') count++;
                else count --;
                if(count == 0) {
                	System.out.println("3: "+(i+1));
                	return i+1+longestValidParentheses3(s.substring(a+i));
                }
            }
            count = 0;
            for(int i = 0 ; i <= b - a ; i++) {
//            	System.out.println("4: "+i+" "+count+" "+s.charAt(b-i));
                if(s.charAt(b-i) == ')') count++;
                else count --;
                if(count == 0) {
                	System.out.println("4: "+(i+1));
                	return (i+1)+longestValidParentheses3(s.substring(a, b-i));
                }
            }
            return -100;
        }
    }
}

